package ru.osu.acm.testing.solutions;

import java.io.*;
import java.util.StringTokenizer;
import java.util.Random;

/**
 * User: Aleksey
 * Date: 16.01.2009
 * Time: 1:51:36
 */
public class Task11 implements Runnable {
    private static BufferedReader br = null;
    private static PrintWriter pw = null;
    private static StringTokenizer st = new StringTokenizer("");

    private void nline() {
        try {
            st = new StringTokenizer(br.readLine());
        }
        catch (IOException e) {
            throw new RuntimeException("RuntimeException");
        }
    }

    private int ni() {
        while (!st.hasMoreTokens()) nline();
        return Integer.parseInt(st.nextToken());
    }

    private long nl() {
        while (!st.hasMoreTokens()) nline();
        return Long.parseLong(st.nextToken());
    }

    private double nd() {
        while (!st.hasMoreTokens()) nline();
        return Double.parseDouble(st.nextToken());
    }

    private String ns() {
        while (!st.hasMoreTokens()) nline();
        return st.nextToken();
    }

    private void solve() {
        /*genTest("input0.txt", "output0.txt", 5, 10, 10, 15);
        genTest("input1.txt", "output1.txt", 10, 10, 10, 30);
        genTest("input2.txt", "output2.txt", 15, 10, 10, 40);
        genTest("input3.txt", "output3.txt", 30, 10, 10, 60);
        genTest("input4.txt", "output4.txt", 40, 100, 100, 100);
        genTest("input5.txt", "output5.txt", 50, 100, 100, 100);
        genTest("input6.txt", "output6.txt", 100, 100, 100, 200);
        genTest("input7.txt", "output7.txt", 100, 100, 100, 1000);
        genTest("input8.txt", "output8.txt", 150, 100, 100, 1500);
        genTest("input9.txt", "output9.txt", 200, 100, 100, 15000);
        genTest("input10.txt", "output10.txt", 250, 1000, 1000, 20000);
        genTest("input11.txt", "output11.txt", 300, 1000, 1000, 20000);*/
        //shit();

        int n = ni();
        int W = ni();
        int[] weights = new int[n];
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = ni();
            values[i] = ni();

        }
        int[] dp = new int[W + 1];
        dp[0] = 0;
        for (int i = 1; i < W; i++) {
            dp[i] = -1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = W; j >= 0; j--) {
                if (dp[j] >= 0 && j + weights[i] <= W && dp[j + weights[i]] < dp[j] + values[i]) {
                    dp[j + weights[i]] = dp[j] + values[i];
                }
            }
        }
        int max = dp[0];
        for (int i = 1; i <= W; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        pw.println(max);
    }

    public void run() {
        solve();
        pw.close();
    }

    public void genTest(String inputFile, String outputFile, int n, int maxWeight, int maxValue, int W) {
        try {
            PrintWriter inp = new PrintWriter(inputFile);
            PrintWriter outp = new PrintWriter(outputFile);

            int[] weights = new int[n];
            int[] values = new int[n];

            Random random = new Random();
            random.setSeed(9329);

            inp.println(n + " " + W);
            for (int i = 0; i < n; i++) {
                weights[i] = random.nextInt(maxWeight) + 1;
                values[i] = random.nextInt(maxValue) + 1;
                inp.println(weights[i] + " " + values[i]);
            }

            int[] dp = new int[W + 1];
            dp[0] = 0;
            for (int i = 1; i < W; i++) {
                dp[i] = -1;
            }

            for (int i = 0; i < n; i++) {
                for (int j = W; j >= 0; j--) {
                    if (dp[j] >= 0 && j + weights[i] <= W && dp[j + weights[i]] < dp[j] + values[i]) {
                        dp[j + weights[i]] = dp[j] + values[i];
                    }
                }
            }
            int max = dp[0];
            for (int i = 1; i <= W; i++) {
                if (dp[i] > max) {
                    max = dp[i];
                }
            }
            outp.println(max);

            inp.close();
            outp.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void shit() {
        int W = 5;
        int n = 2;
        int[] weights = new int[] {4, 5};
        int[] values = new int[] {10, 4};

        int[] dp = new int[W + 1];
        dp[0] = 0;
        for (int i = 1; i < W; i++) {
            dp[i] = -1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = W; j >= 0; j--) {
                if (dp[j] >= 0 && j + weights[i] <= W && dp[j + weights[i]] < dp[j] + values[i]) {
                    dp[j + weights[i]] = dp[j] + values[i];
                }
            }
        }
        int max = dp[0];
        for (int i = 1; i <= W; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
    }

    public static void main(String[] args) {
        /*br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new OutputStreamWriter(System.out));*/
        /**/

        try {
            br = new BufferedReader(new FileReader("knapsackfixed.in"));
            pw = new PrintWriter("knapsackfixed.out");
        }
        catch (FileNotFoundException e) {
            throw new RuntimeException("RuntimeException");
        }

        new Thread(new Task11()).start();
    }
}